#include <bits/stdc++.h>
using namespace std;

/*
2014. 重复 K 次的最长子序列
已解答
困难
相关标签
premium lock icon
相关企业
提示
给你一个长度为 n 的字符串 s ，和一个整数 k 。请你找出字符串 s 中 重复 k 次的 最长子序列 。

子序列 是由其他字符串删除某些（或不删除）字符派生而来的一个字符串。

如果 seq * k 是 s 的一个子序列，其中 seq * k 表示一个由 seq 串联 k 次构造的字符串，那么就称 seq 是字符串 s 中一个 重复 k 次 的子序列。

举个例子，"bba" 是字符串 "bababcba" 中的一个重复 2 次的子序列，因为字符串 "bbabba" 是由 "bba" 串联 2 次构造的，而 "bbabba" 是字符串 "bababcba" 的一个子序列。
返回字符串 s 中 重复 k 次的最长子序列  。如果存在多个满足的子序列，则返回 字典序最大 的那个。如果不存在这样的子序列，返回一个 空 字符串。

 

示例 1：

example 1

输入：s = "letsleetcode", k = 2
输出："let"
解释：存在两个最长子序列重复 2 次：let" 和 "ete" 。
"let" 是其中字典序最大的一个。
示例 2：

输入：s = "bb", k = 2
输出："b"
解释：重复 2 次的最长子序列是 "b" 。
示例 3：

输入：s = "ab", k = 2
输出：""
解释：不存在重复 2 次的最长子序列。返回空字符串。
 

提示：

n == s.length
2 <= k <= 2000
2 <= n < k * 8
s 由小写英文字母组成
*/

// 法一
class Solution {
public:
    string longestSubsequenceRepeatedK(string s, int k) {
        // 存储可能出现在结果中的候选字符
        vector<char> candidates;
        // 统计每个字符的出现次数
        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }
        // 筛选出出现次数 >= k 的字符作为候选
        for (int i = 0; i < 26; i++) {
            if (count[i] >= k) {
                candidates.push_back('a' + i);
            }
        }
        // 如果没有候选字符，直接返回空字符串
        if (candidates.empty()) return "";
        
        // 使用队列进行BFS，初始状态为空字符串
        queue<string> q;
        q.push("");
        string ans = "";
        
        // BFS遍历所有可能的子序列
        while (!q.empty()) {
            string curr = q.front();
            q.pop();
            
            // 尝试在当前子序列后添加每个候选字符
            for (char c : candidates) {
                string next = curr + c;
                // 检查添加后的子序列是否能重复k次
                if (isSubsequenceRepeatedK(s, next, k)) {
                    // 更新答案并继续扩展
                    ans = next;
                    q.push(next);
                }
            }
        }
        
        return ans;
    }
    
    // 检查seq是否能在s中重复k次
    bool isSubsequenceRepeatedK(const string& s, const string& seq, int k) {
        // 空序列默认满足条件
        if (seq.empty()) return true;
        int n = s.size();
        int m = seq.size();
        int i = 0;      // 当前匹配到seq的位置
        int repeat = 0; // 已匹配的重复次数
        
        // 遍历原字符串s
        for (int j = 0; j < n; j++) {
            if (s[j] == seq[i]) {
                i++;
                // 完成一次seq的匹配
                if (i == m) {
                    repeat++;
                    i = 0;  // 重置seq的匹配位置
                    if (repeat == k) return true;
                }
            }
        }
        
        return false;
    }
};

// 法二
class Solution {
    string tmp;         // 存储可能的候选字符（按字典序降序排列）
    string ans;         // 记录最长的有效重复子序列
    int cnt[26] = {0};  // 统计每个字符的出现次数
    char longest_list[8]; // 存储当前尝试的子序列（最大长度为7）
public:
    // 检查从0到index位置的字符组成的子序列是否能在s中重复k次
    bool check(const int& index, const string &s, const int &k){
        char c;
        size_t len;
        int pos = 0;  // 记录当前搜索位置
        
        // 尝试找到k个完整的子序列副本
        for(int i = 0; i < k; i++){
            for(int j = 0; j < index; j++){
                c = longest_list[j];
                // 从pos位置开始查找字符c
                len = s.find_first_of(c, pos);
                if(len == string::npos){
                    return false;  // 未找到，子序列无效
                }
                pos = len + 1;  // 更新搜索起始位置
            }
        }
        return true;  // 成功找到k个副本
    }
    
    // 深度优先搜索可能的子序列
    void dfs(string &s, int &k, const int &index){
        // 尝试所有候选字符
        for(const auto e : tmp){
            longest_list[index] = e;  // 选择当前字符
            
            // 检查条件：
            // 1. 该字符剩余次数足够组成k个子序列
            // 2. 当前子序列能在s中重复k次
            if(cnt[longest_list[index] - 'a'] >= k && check(index + 1, s, k)){
                cnt[longest_list[index] - 'a'] -= k;  // 消耗k次该字符
                
                // 更新最长有效子序列
                if(index + 1 > ans.size()){
                    ans = string(longest_list, longest_list + index + 1);
                }
                
                // 递归搜索更长的子序列
                dfs(s, k, index + 1);
                
                // 回溯：恢复该字符的使用次数
                cnt[longest_list[index] - 'a'] += k;
            }
        }
        return;
    }
    
    string longestSubsequenceRepeatedK(string s, int k) {
        // 统计每个字符的出现次数
        for(const auto c : s){
            cnt[c - 'a']++;
        }
        
        // 构建候选字符集（按字典序降序排列）
        for(int i = 25; i >= 0; i--){
            if(cnt[i] >= k){
                tmp.push_back(i + 'a');
            }
        }
        
        // 从空序列开始深度优先搜索
        dfs(s, k, 0);
        
        return ans;
    }
};
